222. 完全二叉树的节点个数

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var countNodes = function(node) {
    // 感觉就是标准的遍历, 层次遍历写过一次了, 这次写个递归的吧. 先序遍历
    // 这里的前中后遍历, 就是 1 的位置不同而已
    if (node === null) return 0;
    else return 1 + countNodes(node.left) + countNodes(node.right);
};

方案二: 层次遍历

var countNodes = function(node) {
    const queue = [node];
    let count = 0;

    while (queue.length > 0) {
        const n = queue.pop();

        if (n !== null) {
            count++;
            queue.push(n.right);
            queue.push(n.left);
        }
    }

    return count;
};

方案三: 利用完全二叉树的特点

计算子数的高度, 只要左右的高度相等, 就可以直接根据层数计算出节点数

但是难点在于如何避免子树的高度反复计算

所以可以反过来, 利用递归从终止条件开始的特点, 先算最底层的节点是否是满二叉树, 再回到上层就知道是不是了

但是这样的话, 就和普通的遍历一样了, 还是没有利用到完全二叉树的特点.

所以能依赖的就只有 depth 变量的传递和维护

var countNodes = function(node, leftDepth = 0, rightDepth = 0) {
    // 递归从终止条件开始想
    if (node === null) return 0;

    // 计算左右子数的深度, 上层计算有效就跳过
    if (leftDepth <= 0) {
        leftDepth = 0;
        let leftNode = node.left;
        while (leftNode !== null) {
            leftDepth++;
            leftNode = leftNode.left;
        }
    }

    if (rightDepth <= 0) {
        rightDepth = 0;
        let rightNode = node.right;
        while (rightNode !== null) {
            rightDepth++;
            rightNode = rightNode.right;
        }
    }

    if (leftDepth === rightDepth) return (2 << leftDepth) - 1;

    return 1 + countNodes(node.left, leftDepth - 1, 0) + countNodes(node.right, 0, rightDepth - 1);
};